package leetcode;

public class LC50 {
    public static void main(String[] args) {
        LC50 lc50 = new LC50();
        System.out.println(lc50.searchInsert1(new int[]{1, 3, 5, 7, 8, 23, 55}, 56));
        System.out.println(lc50.searchInsert1(new int[]{1, 3, 5, 7, 8, 23, 55}, 9));
        System.out.println(lc50.searchInsert1(new int[]{1, 3, 5, 7, 8, 23, 55}, 0));
    }

    //顺序查找
    public int searchInsert(int[] nums, int target) {
        for(int i = 0; i< nums.length; i++){
            if(nums[i] >= target) return i;
        }
        return nums.length;
    }
    // 二分查找
    public int searchInsert1(int[] nums, int target) {
        int first = 0;
        int last = nums.length - 1;
        while(first <= last){
            int index = (first+last)/2;
            if (nums[index] == target) return index;
            if (nums[index] > target) last = --index;
            else first = ++index;
        }
        return first;
    }
}
